package Hash;

import org.junit.Test;

import java.util.*;


public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] arr =new int[26];
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a'] ++;
        }
        for (int i = 0; i < t.length(); i++) {
            if(arr[t.charAt(i) - 'a']-- == 0){
                return false;
            }
        }
        return true;

        //        HashSet<Character> set = new HashSet<>();
//        for (int i = 0; i < t.length(); i++) {
//            set.add(t.charAt(i));
//        }
//        for (int i = 0; i < s.length(); i++) {
//            if (!set.contains(s.charAt(i))) {
//                return false;
//            }
//            set.remove(s.charAt(i));
//        }
//        return set.isEmpty();

    }
    int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> set1 = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])) {
                set1.add(nums2[i]);
            }
        }
        int[] ans = new int[set1.size()];
        int index = 0;
        for(int i :  set1){
            ans[index++] = i;
        }
        return ans;
}

    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        //计算平方和
        int sum = 0;
        while (sum != 1){
            sum = 0;
            while (n != 0) {
                sum += Math.pow(n % 10, 2);
                n = n / 10;
            }
            n = sum;
            if (!set.add(sum)) {
                return false;
            }
        }
        return true;
    }
    //使用哈希表
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{1,1};
//        int[] arr = new int[10001];
//        for (int i = 0; i < nums.length; i++) {
//            if (i == 0) {
//                arr[nums[i]] = -1;
//            } else {
//                arr[nums[i]] = i;
//            }
//        }
//        for (int j = 0; j < nums.length; j++) {
//            if (arr[target - nums[j]] != 0) {
//                if (arr[target - nums[j]] == -1) {
//                    return new int[]{0, j};
//                }
//                return new int[]{j, arr[target - nums[j]]};
//            }
//        }
//        return new int[]{};
    }
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i : nums1) {
            for (int j : nums2) {
                int ij = i + j;
                if (map1.containsKey(ij)) {
                    map1.put(ij, map1.get(ij) + 1);
                } else {
                    map1.put(ij, 1);
                }
            }
        }
        int ans = 0;
        for (int i : nums3) {
            for (int j : nums4) {
                if (map1.containsKey(i + j)) {
                    ans += map1.get(i + j);
                }
            }
        }
        return ans;
    }
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] arr = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            arr[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if(arr[ransomNote.charAt(i) - 'a']-- == 0){
                return false;
            }
        }
        return true;
    }
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int left;

        int right;
        for (int i = 0; i < nums.length; i++) {
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    List<Integer> listTmp = new ArrayList<>();
                    listTmp.add(nums[i]);
                    listTmp.add(nums[left]);
                    listTmp.add(nums[right]);
                    list.add(listTmp);
                    left++;
                } else if (sum > 0) {
                    left++;
                } else {
                    right--;
                }
            }

        }
        return list;
    }
    @Test
    public void fourSum() {
        // -2 -1 0 0 1 2
        int[] nums = new int[]{1, 0, -1, 0, -2 ,2}; int target = 0;
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //去重i
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //j循环
            for (int j = i + 1; j < nums.length; j++) {
                //去重j
                if (nums[j] == nums[j - 1]){
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                //left与right循环
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> listTmp = new ArrayList<>();
                        listTmp.add(nums[i]);
                        listTmp.add(nums[j]);
                        listTmp.add(nums[left]);
                        listTmp.add(nums[right]);
                        list.add(listTmp);
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                    }
                    else if (sum < target) {
                        left++;
                    }
                    else {
                        right--;
                    }
                }
            }

        }
        for(List<Integer> i :list){
            for(int j :i){
                System.out.print(j+" ");
            }
        }
    }
}
